package summary;

import java.util.Stack;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/4 20:22
 * https://leetcode.cn/problems/maximal-square/
 */
public class Title221 {



    public static int maximalSquare(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] height = new int[m];
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    height[j] += 1;
                }else{
                    height[j] = 0;
                }
            }
            max = Math.max(max, dfs(height));
        }
        return max;
    }

    private static int dfs(int[] height) {
        int n = height.length;
        int[] newHeight = new int[n + 2];
        for (int i = 0; i < n; i++) {
            newHeight[i + 1] = height[i];
        }
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < newHeight.length; i++) {
            while (!stack.isEmpty() && newHeight[i] < newHeight[stack.peek()]) {
                int mid = stack.pop();
                int left = stack.peek();
                int h = newHeight[mid];
                int w = i - left - 1;
                if (w > h) {
                    max = Math.max(max, h * h);
                    break;
                } else if (h > w) {
                    max = Math.max(max, w * w);
                    continue;
                }
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
    }

    public static void main(String[] args) {
        char[][] height = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        maximalSquare(height);
    }
}
